package org.example;

import java.util.Arrays;

public class Test3 {
    //leetcode 452 用最少数量的箭引爆气球 https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

    /**
     * 先将points按照points[n][0]升序排列
     * 然后遍历数组，求当前气球和前面未引爆的气球，弓箭能够引爆的区间，也就是start=Math.max(start,points[n][0])
     * end = Math.min(end,points[1])，如果区间不存在，也就是start>end，那么当前气球就不能和之前未引爆的气球一起引爆
     * 那么就ans++，当前气球和后面的气球一起引爆，重置区间为start=points[n][0],end=points[n][1]
     * @param points
     * @return
     */
    public int findMinArrowShots(int[][] points) {
        int start = Integer.MIN_VALUE, end = Integer.MAX_VALUE;
        int ans = 1;
        Arrays.sort(points,(a, b) -> {
            return a[0] - b[0];
        });
        for (int i = 0; i < points.length; i++) {
            start = Math.max(start,points[i][0]);
            end = Math.min(end,points[i][1]);
            if (start > end) {
                ans++;
                start = points[i][0];
                end = points[i][1];
            }
        }
        return ans;
    }
}
